#include <bits/stdc++.h>
using namespace std;

#define FOR_INC(i, start, end) for (int i = start; i < end; ++i)
#define FOR_DEC(i, start, end) for (int i = start; i > end; --i)
#define FOR_INC_EQUAL(i, start, end) for (int i = start; i <= end; ++i)
#define FOR_DEC_EQUAL(i, start, end) for (int i = start; i >= end; --i)
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL)
    {
    }
};

// bool cmp(ListNode *a, ListNode *b)
// {
//     return a->val < b->val;
// }
// class Solution
// {
//   public:
//     ListNode *sortInList(ListNode *head)
//     {
//         // write code here
//         if (head == nullptr)
//         {
//             return nullptr;
//         }
//         vector<ListNode *> vector1;
//         while (head != nullptr)
//         {
//             vector1.emplace_back(head);
//             head = head->next;
//         }
//         sort(vector1.begin(), vector1.end(), cmp);
//         auto ans = vector1[0];
//         for (int i = 0; i < vector1.size() - 1; ++i)
//         {
//             vector1[i]->next = vector1[i + 1];
//         }
//         vector1[vector1.size() - 1]->next = nullptr;
//         return ans;
//     }
// };
// int main()
// {
//     int a;
//     Solution s;
//     Solution *p =
//         new Solution(); //
//         创建指针，指针指向的对象占用的内存会在堆区。如果在函数里创建对象，会占用栈区的内存。
//     return 0;
// }

bool cmp(ListNode* e1, ListNode* e2)
{
    return e1->val < e2->val;
}
class Solution
{
  public:
    ListNode *sortInList(ListNode *head)
    {
        // write code here
        if (head == nullptr)
        {
            return nullptr;
        }
        vector<ListNode *> arr;
        while (head)
        {
            arr.emplace_back(head);
            head = head->next;
        }
        sort(arr.begin(), arr.end(), cmp);
        for (int i = 0; i < arr.size() - 1; i++)
        {
            arr[i]->next = arr[i + 1];
        }
        auto ans = arr[0];
        arr[arr.size() - 1]->next = nullptr;//链表末尾要接上空指针否则会打印很多数据，因为不知道链表的终点
        return ans;
    }
};